/*
 * @Descripttion:
 * @version:
 * @Author: xiaozilai
 * @Date: 2022-11-04 21:30:53
 * @LastEditors: xiaozilai
 * @LastEditTime: 2022-11-05 09:47:10
 */
/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 *
 * https://leetcode.cn/problems/subsets-ii/description/
 *
 * algorithms
 * Medium (63.68%)
 * Likes:    953
 * Dislikes: 0
 * Total Accepted:    254K
 * Total Submissions: 398.9K
 * Testcase Example:  '[1,2,2]'
 *
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 *
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 *
 *
 * 示例 2：
 *
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1
 * -10
 *
 *
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        vector<vector<int>> ans;
        vector<int> temp;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        dfs(nums, temp, ans, 0, n);
        return ans;
    }

    void dfs(vector<int> &nums, vector<int> &temp, vector<vector<int>> &ans, int index, int n) {
        if (index == n) {
            ans.push_back(temp);
            return;
        }
        // 重复
        if (index < n - 1 && nums[index] == nums[index + 1]) {
            int end_index = index + 1;
            while (end_index < n && nums[end_index] == nums[index]) {
                ++end_index;
            }
            int repeat_cnt = end_index - index;
            for (int i = 0; i <= repeat_cnt; ++i) {
                if (i != 0) {
                    temp.push_back(nums[index]);
                }
                dfs(nums, temp, ans, end_index, n);
            }
            while (repeat_cnt--) {
                temp.pop_back();
            }
        } else {
            dfs(nums, temp, ans, index + 1, n);
            temp.push_back(nums[index]);
            dfs(nums, temp, ans, index + 1, n);
            temp.pop_back();
        }
    }
};
// @lc code=end
